#include <vector>
using namespace std;

void InsertSort(vector<int>& v)
{
	int sz = v.size(), j;
	for(int i = 1; i < sz; i++)
	{
		j = i;
		while(j > 0)
		{
			if(v[j] < v[j - 1]) swap(v[j], v[j - 1]);
			else break;
			j--;
		}
	}
}

void SheelSort(vector<int>& v)
{
	int sz = v.size(), j;
	for(int gap = sz / 3 + 1; gap > 0; gap /= 3)
	{
		for(int i = gap; i < sz; i += gap)
		{
			int j = i;
			while(j >= gap)
			{
				if(v[j] < v[j - gap]) swap(v[j], v[j - gap]);
				else break;
				j -= gap;
			}
		}
	}
}
